1703G - Good Key Bad Key - CodeForces Solution

bitmasks brute force dp greedy math *1600

Please click on ads to support us..

Python Code: 

from itertools import accumulate as ac;r=lambda:map(int,input().split());t,=r();f=lambda i:p[i]-k*i+sum(a[i+j]>>(j+1)for j in range(min(n-i,30)))
while t:t-=1;n,k=r();a=[*r()];p=[0]+list(ac(a));print(max(f(i)for i in range(n+1)))

C++ Code: 

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

void solve() {
    int n, k;
    cin >> n >> k;

    vector<ll> a(n);
    for (auto &x: a) cin >> x;

    vector<vector<ll>> dp(n + 1, vector<ll>(31, -1e18));
    dp[0][0] = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= min(i + 1, 30); j++) {
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - k + (a[i] / (1 << j)));
            int nxt = min(30, j + 1);
            dp[i + 1][nxt] = max(dp[i + 1][nxt], dp[i][j] + (a[i] / (1 << nxt)));
        }
    }

    cout << *max_element(dp[n].begin(), dp[n].end());
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;

    while (t--) {
        solve();
        cout << '\n';
    }
}


Comments

Submit
0 Comments
More Questions

One String No Trouble
Help Jarvis!
Lift queries
Goki and his breakup
Ali and Helping innocent people
Book of Potion making
Duration
Birthday Party
e-maze-in
Bricks Game
Char Sum
Two Strings
Anagrams
Prime Number
Lexical Sorting Reloaded
1514A - Perfectly Imperfect Array
580A- Kefa and First Steps
1472B- Fair Division
996A - Hit the Lottery
MSNSADM1 Football
MATCHES Playing with Matches
HRDSEQ Hard Sequence
DRCHEF Doctor Chef
559. Maximum Depth of N-ary Tree
821. Shortest Distance to a Character
1441. Build an Array With Stack Operations
1356. Sort Integers by The Number of 1 Bits
922. Sort Array By Parity II
344. Reverse String
1047. Remove All Adjacent Duplicates In String